﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphPackage
{
    //  Stefan 21.11.2011
    public class BasicGraphImpl:IBasicGraph
    {
        private IList<Vertex> _vertices;

        public BasicGraphImpl()
        {
            _vertices = new List<Vertex>();
        }

        public void AddVertex(Vertex vertex)
        {
            _vertices.Add(vertex);
        }

        public void AddEdge(Vertex startVertex, Vertex endVertex)
        {
            startVertex.AddEdge(endVertex);
        }

        public void RemoveVertex(Vertex v)
        {
            //remove vertex
            _vertices.Remove(v);
            //remove edges
            IEnumerator<Vertex> it = Vertices();
            while (it.MoveNext())
            {
                Vertex currVertex = it.Current;
                IList<Edge> edges = currVertex.Edges();
                int i = 0;
                while (i < edges.Count)
                {
                    Edge e = edges[i];
                    if (e.To.Equals(v))
                    {
                        edges.Remove(e);
                    }
                    else
                    {
                        i++;
                    }
                }
            }
        }

        public void RemoveEdge(Vertex from, Vertex to)
        {
            Edge e = FindEdge(from, to);
            if (e != null)
                e.From.RemoveEdge(e);
        }

        public bool ContainsVertex(Vertex vertex)
        {
            bool found = false;
            IEnumerator<Vertex> i = Vertices();
            while (i.MoveNext() && !found)
            {
                Vertex w = i.Current;
                if (w.Name.Equals(vertex.Name))
                    found = true;
            }
            return found;
        }

        public bool IsAdjacent(Vertex startVertex, Vertex endVertex)
        {
            return (FindEdge(startVertex, endVertex) != null);
        }

        public IList<Vertex> GetAdjacencies(Vertex vertex)
        {
            Vertex w = _vertices[_vertices.IndexOf(vertex)];
            IList<Edge> temp = w.Edges();
            IList<Vertex> returnList = new List<Vertex>();
            foreach (Edge e in temp)
            {
                returnList.Add(e.To);
            }
            return returnList;
        }

        public IEnumerator<Vertex> Vertices()
        {
            return _vertices.GetEnumerator();
        }

        public IEnumerator<Edge> Edges()
        {
            IList<Edge> allEdges = new List<Edge>();
            foreach (Vertex v in _vertices)
            {
                IEnumerator<Edge> edges = v.Edges().GetEnumerator();
                while (edges.MoveNext())
                {
                    allEdges.Add(edges.Current);
                }
            }
            return allEdges.GetEnumerator();
        }

        public bool IsEmpty()
        {
            return _vertices.Count == 0;
        }

        public int GetNoOfVertices()
        {
            return _vertices.Count;
        }

        public int GetNoOfEdges()
        {
            int result = 0;
            foreach (Vertex v in _vertices)
            {
                result = result + v.OutDegree();
            }
            return result;
        }

        public void Clear()
        {
            _vertices = new List<Vertex>();
        }

        public IList<Vertex> DepthFirstSearch(Vertex v)
        {	
            UnMark();//Make sure that all vertices are marked unvisited
            IList<Vertex> returnList = new List<Vertex>();
            Stack<Vertex> s = new Stack<Vertex>();
            v.Mark = true;
            returnList.Add(v);
            s.Push(v);

            while (s.Count != 0)
            {
                Vertex w = s.Peek();
                IList<Vertex> adjList = this.GetAdjacencies(w);
                Vertex u = GetNextUnMarked(adjList);
                if (u != null)//There are unvisited neighbours
                {
                    u.Mark = true;
                    returnList.Add(u);
                    s.Push(u);
                }
                else
                    s.Pop();
            }
            return returnList;
        }

        private Edge FindEdge(Vertex from, Vertex to)
        {	
            //POST	returns null if there is no edge(from,to)
            Edge currEdge = null; ;
            bool found = false;
            IEnumerator<Edge> i = from.Edges().GetEnumerator();
            while (!found && i.MoveNext())
            {
                currEdge = i.Current;
                if (currEdge.To.Equals(to))
                    found = true;
            }
            if (found)
                return currEdge;
            else
                return null;
        }

        private void UnMark()
        {
            for (int i = 0; i < _vertices.Count; i++)
                (_vertices[i]).Mark = false;
        }

        private Vertex GetNextUnMarked(IList<Vertex> list)
        {	
            bool found = false;
            int i = 0;
            Vertex v = null;
            while (!found && i < list.Count)
            {
                v = list[i];
                if (!v.Mark)
                    found = true;
                else
                    i++;
            }
            if (found)
                return v;
            else
                return null;
        }
    }
}
